/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/sort-colors
   @Language: C++
   @Datetime: 19-07-05 12:32
   */

// Method 1, traversal twice, Time O(n), Space O(1), Time 4ms
class Solution {
public:
	void sortColors(vector<int>& nums) {
		int colors[3]={0,0,0};
		for(int i=nums.size(); i--; ++colors[nums[i]]);
		for(int c=0, i=0; c<3; ++c)
			for(; colors[c]--; nums[i++]=c);
	}
};


// Method 2, 3 partitions, Time 8ms
class Solution {
public:
	void sortColors(vector<int>& nums) {
		for(int zero=-1, i=0, two=nums.size(); i<two; ++i)
			if(nums[i]==0) swap(nums[++zero],nums[i]);
			else if(nums[i]==2) swap(nums[--two],nums[i--]);
	}
};
